/*
 * @lc app=leetcode.cn id=287 lang=cpp
 *
 * [287] 寻找重复数
 */

// #include <iostream>
// #include <vector>
// #include <set>
// using namespace std;

// @lc code=start
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int result = 0;
        int fast = 0;
        int slow = 0;

        // 使用快慢指针寻找环路
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        
        // Floyd算法寻找环路的起始节点，即重复的数
        int pre1 = 0;
        int pre2 = slow;
        while (pre1 != pre2) {
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }

        return pre1;
    }
};
// @lc code=end

